#include <stdio.h>
#include <stdlib.h>

// 链表中节点结构
typedef struct Link
{
    int elem;
    struct Link* next;
}link;

link* initLink()
{
    int i;
    link* p = NULL; //创建头指针
    link* temp = (link*)malloc(sizeof(link)); //创建首元节点
    // 首元节点初始化
    temp->elem = 1;
    temp->next = NULL;
    p = temp; //头指针指向首元节点
    for(i=2;i<5;i++)
    {
        link* a = (link*)malloc(sizeof(link));
        a->elem = i;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }
    return p;  // 返回头指针
}

void display(link* p)
{
    link* temp = p;
    while (temp)
    {
        printf("%d ", temp->elem);
        temp = temp->next;
    }
    printf("\n");
}

// 带头结点的链表
link* initHeadLink()
{
    int i;
    // 创建一个头结点
    link* p = (link*)malloc(sizeof(link));
    // 声明一个指针指向头结点
    link* temp = p;
    // 生成链表
    for(i = 1; i<5; i++)
    {
        link* a = (link*)malloc(sizeof(link));
        a->elem = i;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }
    return p;
}

void displayHeadLink(link* p)
{
    link* temp = p;
    while (temp->next)
    {
        temp = temp->next;
        printf("%d ", temp->elem);
    }
    printf("\n");
}

// 插入链表
void insertLink(link* p, int elem, int index)
{
    link* temp = p;
    link* insert = NULL;
    int i;
    for(i=1;i<index;i++)
    {
        temp = temp->next;
        if(temp == NULL)
        {
            printf("插入位置异常！！！\n");
            return ;
        }
    }
    // 创建插入元素
    insert = (link*)malloc(sizeof(link));
    insert->elem = elem;
    insert->next = temp->next;
    temp->next = insert;
}

// 删除链表节点
void delLink(link* p, int elem)
{
    link* temp = p;
    link* pro;
    while(temp->next)
    {
        pro = temp;
        temp = temp->next;
        if(elem == temp->elem)
        {
            pro->next = temp->next;
            free(temp);
            temp = NULL;
            return ;
        }
    }
    printf("要删除的元素不存在！\n");
}

// 查找
int searchLink(link* p, int elem)
{
    link* temp = p;
    int i = 1;
    while (temp->next)
    {
        temp = temp->next;
        if(elem == temp->elem)
        {
            return i;
        }
        i++;
    }
    return -1;
}

// 修改链表节点
void updateLink(link* p, int index, int newElem)
{
    int i = 0;
    link* temp = p;
    temp = temp->next;  // 指向首元节点
    for(i=1; i<index; i++)
    {
        if(temp == NULL)
        {
            printf("修改的位置越界...\n");
            return ;
        }
        temp = temp->next;
    }
    temp->elem = newElem;
}

int main()
{
    // link* p = NULL;
    // // 初始化链表
    // p = initLink();
    // printf("不带头结点链表\n");
    // display(p);
    link* ph = NULL;
    // 初始化带头结点链表
    ph = initHeadLink();
    printf("带头结点链表\n");
    displayHeadLink(ph);
    // 插入节点
    printf("2处插入100\n");
    insertLink(ph, 100, 2);
    displayHeadLink(ph);
    // 删除节点
    printf("删除节点2\n");
    delLink(ph, 2);
    displayHeadLink(ph);
    // 查找节点
    printf("查找节点1\n");
    int search = searchLink(ph, 1);
    printf("1位于链表第%d个节点\n", search);
    // 修改节点
    printf("修改位置3的节点为-1\n");
    updateLink(ph, 3, -1);
    displayHeadLink(ph);
    return 0;
}